#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/12/11 14:17
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 高级-螺旋矩阵.py
# @Software: PyCharm
from utils.main import main, opt_list


class Solution:
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        op = [
            (0, 1),
            (1, 0),
            (0, -1),
            (-1, 0)
        ]
        m = {}
        n0 = len(matrix)
        if not n0:
            return []
        n1 = len(matrix[0])
        n = n0 * n1
        x, y = 0, 0
        ans = []
        if not m.get((x, y)):
            m[(x, y)] = 1
            ans.append(matrix[x][y])
            n -= 1
        i = 0
        while n > 0:
            xx = x + op[i][0]
            yy = y + op[i][1]
            if 0 <= xx < n0 and 0 <= yy < n1 and not m.get((xx, yy)):
                x, y = xx, yy
                m[(x, y)] = 1
                ans.append(matrix[x][y])
                n -= 1
            else:
                i += 1
                i %= 4
                continue
        return ans


def opt(matrix):
    solve = Solution()
    print(matrix)
    print('ans:')
    print(solve.spiralOrder(matrix))


def opt1():
    matrix = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]
    ]
    opt(matrix)


def opt2():
    matrix = [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12]
    ]
    opt(matrix)


def opt3():
    matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
    opt(matrix)
    print('right:')
    print([1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10])


if __name__ == '__main__':
    opt_list.append(opt1)
    opt_list.append(opt2)
    opt_list.append(opt3)
    main()

